home *** CD-ROM | disk | FTP | other *** search
/ L' Effet Pommier 3 / L'Effet Pommier - Volume 03.iso / Programmation / gray image 2.1 / fractal_map.cc < prev    next >
Text File  |  1995-05-31  |  5KB  |  146 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *               Generating Fractal Maps
  6.  *
  7.  * The algorithm is based on (but *only* based on) the following
  8.  * explanation described in the "documentation" to program MARS 
  9.  * (Tim Clarke, tjc1005@hermes.cam.ac.uk, posted in some "games"
  10.  * group)
  11.  *
  12.  * "This is a recursive subdivision, or plasma, fractal. You start of
  13.  * with a random height at (0,0) and therefore also at (256,0), (0,256),
  14.  * (256,256).  Call a routine that takes as input the size and position
  15.  * of a square, in the first case the entire map.
  16.  * This routine get the heights from the corners of the square it gets
  17.  * given.  Across each edge (if the map has not been written to at the
  18.  * point halfway along that edge), it takes the average of the heights of
  19.  * the 2 corners on that edge, applies some noise proportional to the
  20.  * length of the edge, and writes the result into the map at a position
  21.  * halfway along the edge. The center of the square is the average of the
  22.  * four corners+noise.
  23.  * The routine then calls itself recursively, splitting each square into
  24.  * four quadrants, calling itself for each quadrant until the length of
  25.  * the side is 2 pixels.
  26.  * This is probably old-hat to many people, but the map is made more
  27.  * realistic by blurring [applying some filter to it]
  28.  * The colors are done so that the sun is on the horizon to the East:
  29.  *     Color=A*[ w(u+1,v)-w(u,v) ]+B
  30.  * with A and B chosen so that the full range of the palette is used.
  31.  * The sky is a similar fractal but without the colour transformation"
  32.  * <EOQ>
  33.  *
  34.  * The first distinction is the present program is that the algorithm
  35.  * is iterative rather than recursive. For another thing, our map is
  36.  * *NOT* periodic. BTW, it lets us use seeds in every corner of a map
  37.  * (which would create "biased" clouds).
  38.  *
  39.  * Note that a map's pixel value is computed average + noise, scaled up to
  40.  * the current dim. So when 2*scale > max pixel value, we've got a problem.
  41.  * To get around that, the scale factor of the noise is chosen not
  42.  * to exceed max_pixel_value/2.
  43.  *
  44.  * Since map is not-periodical, if a pixel sticks out of the map,
  45.  * we force it within: say, when we need to operate map(2^order,j),
  46.  * we actually dealing with map((2^order)-1,j), etc.
  47.  *
  48.  * $Id: fractal_map.cc,v 2.0 1995/03/16 21:18:01 oleg Exp oleg $
  49.  *
  50.  ************************************************************************
  51.  */
  52.  
  53. #ifdef __GNUC__
  54. #pragma implementation "fractal_map.h"
  55. #endif
  56.  
  57. #include "fractal_map.h"
  58. #include <minmax.h>
  59. #include "std.h"
  60.  
  61.                 // Get some noise with a dispersion 'scale'
  62.                 // (which is assumed to be a power of 2)
  63.                 // and average 0
  64.                 // Say, if scale=2 return either 0 or 1
  65.                 // if scale=128, return a random number
  66.                 // within [-64,63]
  67.                 // Note, that usually a couple of low-order
  68.                 // bits of Random() are "less" random;
  69.                 // therefore, we shift them out.
  70. inline int FractalMap::get_noise(const card scale) const
  71. {
  72. #ifdef __SC__
  73.   return ((Random() >> 2) & (scale-1)) - scale/2;
  74. #else
  75.   return ( rand() & (scale-1) ) - scale/2;
  76. #endif
  77. }
  78.  
  79. FractalMap::FractalMap
  80.     (const card order, const Seeds& _seeds, const card bits_per_pixel)
  81.     : LazyImage(1<<order,1<<order,bits_per_pixel),
  82.       seeds(_seeds)
  83. {
  84.   if( order < 2 || order > 14 )
  85.     _error("Order %d of the desired fractal map is unusual, "
  86.        "I prefer something within [2,14]",order);
  87. }
  88.  
  89. //------------------------------------------------------------------------
  90. //        Here where the map is really constructed
  91.  
  92. void FractalMap::fill_in(IMAGE& im) const
  93. {
  94.   const card largest_noise_scale = 1<<(im.q_depth()-1);
  95.   const card pixel_mask = (1<<im.q_depth())-1;
  96.   const card dim = im.q_nrows();
  97.  
  98.   im(0,0) = seeds.s00;                // Seed the map
  99.   im(dim-1,0) = seeds.s10;
  100.   im(0,dim-1) = seeds.s01;
  101.   im(dim-1,dim-1) = seeds.s11;
  102.  
  103.   for(register card scale=dim; scale>1; scale >>= 1)
  104.   {
  105.     const card scale_half = scale>>1;
  106.     const card noise_scale = min(scale,largest_noise_scale);
  107.     register int i,j;
  108.     for(i=0; i<dim; i += scale)
  109.     {
  110.       int i_up = min(i+scale,dim-1);
  111.       int i_hp = i+scale_half;
  112.       int corner00 = im(i,0);            // caching
  113.       int corner10 = im(i_up,0);
  114.       int mid30 = im(i_hp,0) = 
  115.     (((corner00+corner10)>>1) + get_noise(noise_scale)) & pixel_mask;
  116.       for(j=0; j<dim; j += scale)
  117.       {
  118.     int j_up = min(j+scale,dim-1);
  119.     int j_hp = j+scale_half;
  120.     const int corner01 = im(i,j_up);
  121.     const int corner11 = im(i_up,j_up);
  122.     const int mid03 = i == 0 ? 
  123.               ( ((corner00+corner01)>>1) + 
  124.                 get_noise(noise_scale) ) & pixel_mask : im(i,j_hp);
  125.     const int mid31 = ( ((corner01+corner11)>>1) + 
  126.                 get_noise(noise_scale) ) & pixel_mask;
  127.     const int mid13 = ( ((corner10+corner11)>>1) + 
  128.                 get_noise(noise_scale) ) & pixel_mask;
  129.     const int mid33 = ( ((mid30+mid03+mid31+mid13)>>2) + 
  130.                 get_noise(noise_scale) ) & pixel_mask;
  131.     im(i_hp,j_up) = mid31;
  132.     if( i == 0 )
  133.       im(i,j_hp) = mid03;
  134.     im(i_up,j_hp) = mid13;
  135.     im(i_hp,j_hp) = mid33;
  136.                 // Note, corner01 for col j becomes
  137.     corner00 = corner01;    // corner00 for the next j
  138.     corner10 = corner11;
  139.     mid30    = mid31;
  140.       }
  141.     }
  142.   }
  143. }
  144.  
  145.  
  146.